package protect.week04;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/23 10:27
 * @package protect.week04
 * @description 1287. 有序数组中出现次数超过25%的元素
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
 *
 * 请你找到并返回这个整数
 *
 *  
 *
 * 示例：
 *
 * 输入：arr = [1,2,2,6,6,6,6,7,10]
 * 输出：6
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch03_FindSpecialInteger {

    public int findSpecialInteger(int[] arr) {
        double flag = arr.length /4.0;
        int num = 0;

        Map<Integer, Integer> occur = new HashMap<Integer, Integer>();
        for (int x : arr) {
            occur.put(x, occur.getOrDefault(x, 0) + 1);
        }

        Iterator<Map.Entry< Integer, Integer >> iterator = occur.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry< Integer, Integer > entry = iterator.next();

            if (entry.getValue() >= flag){
                num = entry.getKey();
            }
        }

        return num;
    }
}
